"""Given the root of a binary tree, construct a 0-indexed m x n string matrix res that represents a formatted layout of the tree. The formatted layout matrix should be constructed using the following rules:

The height of the tree is height and the number of rows m should be equal to height + 1.
The number of columns n should be equal to 2height+1 - 1.
Place the root node in the middle of the top row (more formally, at location res[0][(n-1)/2]).
For each node that has been placed in the matrix at position res[r][c], place its left child at res[r+1][c-2height-r-1] and its right child at res[r+1][c+2height-r-1].
Continue this process until all the nodes in the tree have been placed.
Any empty cells should contain the empty string "".
Return the constructed matrix res.

 

Example 1:


Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]
Example 2:


Input: root = [1,2,3,null,4]
Output: 
[["","","","1","","",""],
 ["","2","","","","3",""],
 ["","","4","","","",""]]
 

Constraints:

The number of nodes in the tree is in the range [1, 210].
-99 <= Node.val <= 99
The depth of the tree will be in the range [1, 10]."""
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int height(TreeNode* root) {
        if (!root) return 0;
        return max(1+height(root->left), 1+height(root->right));
    }
    vector<vector<string>> printTree(TreeNode* root) {
        int h = height(root) -1;
        int m = h+1;
        int n  = pow(2, m) -1;

        vector<vector<string>> res;
        res.resize(m);
        for (int i = 0; i < m; i++) {
            res[i].resize(n);
            for (int j = 0; j < n; j++) {
                res[i][j] = "";
            }
        }
        queue<std::pair<TreeNode*, vector<int>>> q;
        
        int r = 0;
        int c = (n-1) / 2;
        vector<int> info{0, r, c};
        q.push(make_pair(root, info));
        while(!q.empty()) {
            std::pair<TreeNode*, vector<int>> node_pair = q.front();
            if (node_pair.second[0] == 0) {
                res[r][c] = to_string(node_pair.first->val);
            } else {
                r = node_pair.second[1] + 1;
                c = node_pair.second[2] + node_pair.second[0] * pow(2, h - node_pair.second[1] -1);
                res[r][c] = to_string(node_pair.first->val);
            }
            
            q.pop();
            if (node_pair.first->left) {
                info = vector<int>{-1, r, c};
                q.push(make_pair(node_pair.first->left, info));
            } 
            if (node_pair.first->right) {
                info = vector<int>{1, r, c};
                q.push(make_pair(node_pair.first->right, info));  
            } 
        }
        return res;
    }
};